As known, bar codes contain information encoded by the ratio of the widths and sequence of the black bars and intervening white spaces. The code may be read by rapidly sweeping a spot of light, such as with a rotating mirror, across the entire bar code pattern. Reflection of light from the spaces and absorption of black bars are sensed by the scanner's photodetector causing a varying level signal to be inputted to the decoder. The signal level thus fluctuates with the bars and spaces and is representative of the coded bar pattern. The scanned image is converted to a single bit data stream where the bars and spaces of the printed bar code will be measured by respective clock periods.
The current state of the art in bar code decoding is comprised of decoding in software and in hardware. Software methods are extremely slow in relation to hardware decoding schemes. Currently, a minimum valid bar code bars or spaces are about four pixels in a 400 dpi (dots per inch) system and would take about 400 nanoseconds to complete a run-length-encoded element. Each pixel would be about 1/4 of this and the decoder must be able to process all possible transitions even if it is a single pixel transition. If the succeeding bar code decoder can decode run-length encoded elements at the rate of 200 nanoseconds then single pixel run-length-encoded elements of about 100 nanoseconds would cause an error in processing.
There are a number of applications where a raster of video data of a scanned document contains a bar code that is required to be extracted from the video data at a real-time video rate. In this type of situation, there is a need to decode bi-level and multi-level bar codes continuously from the digital video data. The term "multi-level" bar code refers to all bar code formats that utilize more than two widths for a given bar or space while a bi-level bar code refers to a format that uses only two widths (wide and narrow) for a bar code character.
The following general description of bi-level and multi-level bar codes is in order to understand some of the concepts in the detailed description. There are many bar code formats. Some of the bi-level formats use a combination of wide and narrow bars and wide and narrow spaces. The wide to narrow width ratio of these bi-level bar codes are about 2:1 to 2.2:1. This ratio may vary with print quality or even scanning speed of some systems. Multi-level bar codes encode more data into each bar and space by employing a four-level width format.
There is no fixed size for bar codes, but rather a range of (min/max) for bars or spaces. This requires automatic scaling of the input data in a proportional or ratio metric manner such that specific physical measurements of the bars and spaces are not critical to decoding. Documents that contain additional information regarding this subject can be found in American National Standard For Materials Handling, Document No. NH10.8N-1983 and the Uniform Symbology Specification--USS-128, by the automatic identification manufacturers.
A general description of a target multi-level bar code known as "USS-128" (commonly referred to as code-128 or bar code-128) will be used as an illustration in conjunction with the described embodiments. Bar code-128 is a multi-character bar code that comprises three bars and three spaces per character of the bar code. The overall format of the bar code is that it is made up of a series of individual characters. The format consists of (1) a start character, (2) variable number of data characters, (3) a check character, and (4) a stop character. A quiet zone is sometimes used and is an area of white space with a specified width in front of and/or behind the bar code string.
Each code-128 character consists of 11 "modules". Each character always has three bars and three spaces. Code-128 comprises spaces that have widths of one, two, three or four modules. A bar or space of one "module" is the narrowest bar or space while a bar or space with a module count of 4 is the widest for this code. For a character to be valid, the number of modules for all six bars and spaces must add up to 11 modules and be in the valid code table. Each element or module could be any number of pixels. This depends on the printed physical size of the bar code on the document and the resolution of the scanning device. The minimum specified limit for individual bars or spaces of module length 1 is about 0.007 inches. At 400 dpi (dots-per-inch) for a scanning camera this is 0.0025 inches per pixel, which is approximately three pixels wide for the minimum bar or space width. There are three start codes and one stop code in the USS-128 format. The start code is what is used to lock onto the multiple thresholds used to differentiate between the specific levels of bars or spaces in the bar code.
U.S. Pat. No. 4,873,426, issued Oct. 10, 1989, entitled "Technique for Reading Bar Codes", describes a method whereby a bar code character can be located and decoded from a bit-map image. The decoding is done by a software analysis of the bit-map image being compared to known patterns. Use of any type of software to detect a bar code generally results in much greater decoding times than those compared to methods that do not incorporate a microprocessor to analyze the incoming data to the system.
U.S. Pat. No. 4,687,912, issued Aug. 18, 1987, entitled "Bar Code Reading Method and Apparatus", discloses a method implemented completely in software that assists in the decision-making process for the determination of what is a bar or a space and what level of width is the bar or space. This type of software implementation attempts to provide accurate decoding of bar codes and may have slight variations in the scanning speed or slight variations of the bar code print quality.
U.S. Pat. No. 5,077,463, issued Dec. 31, 1991, entitled "Bar Code Reading Apparatus" discloses a hardware mechanism that is used to detect the margin of guard bars that were found in a specific bar code format. Guard bars, in this instance, are a pair of vertical bars of a specified width with the same width and space between them that are typically located before, after and/or in some formats in the middle of the bar code. Some bar code formats and/or decoders use guard bars as a means for calibrating and setting up the decoder for the bar code characters that are to follow.
U.S. Pat. No. 4,567,361, issued Jan. 28, 1986, entitled "Reticle Bar Code and Method and Apparatus for Reading Same" describes a specific bar code format and apparatus for reading that format and is primarily intended for use in micro-lithographic reticles that are used in semiconductor manufacturing and is not intended to be a public bar code type of format.